package pers.vic.basics.leetcode;

import com.sun.org.apache.bcel.internal.generic.IF_ACMPEQ;
import org.omg.PortableInterceptor.INACTIVE;

import java.util.HashMap;
import java.util.Map;

/**
 * @description: 76. 最小覆盖子串  {@literal https://leetcode-cn.com/problems/minimum-window-substring/}
 * @author Vic.xu
 * @date: 2021/1/12 0012 8:46
 */
public class J0076_H_MinWindow {

    /*
     * 给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。
     * 如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。
     * 注意：如果 s 中存在这样的子串，我们保证它是唯一的答案。
     */
    public static String minWindow(String s, String t) {
        int sLen = s.length();
        int tLen = t.length();
        if (sLen < tLen) {
            return s.equals(t) ? s : "";
        }
        Map<Character, Integer> tMap = new HashMap<>();
        for (int i = 0; i < tLen; i++) {
            tMap.put(t.charAt(i), tMap.getOrDefault(t.charAt(i), 0) + 1);
        }
        Map<Character, Integer> smap = new HashMap<>();
        String cur = s.substring(0, tLen);
        int start = 0;
        boolean startFlag = false;
        String result = "";
        for (int i = 0; i < sLen; i++) {
            Character c = s.charAt(i);
            if (!startFlag && tMap.containsKey(c)) {
                start = i;
                startFlag = true;
            }

            if (tMap.containsKey(c)) {
                smap.put(s.charAt(i), smap.getOrDefault(s.charAt(i), 0) + 1);
            }
            //当前探测到的子字符串是否能匹配t
            if (!match(tMap, smap)) {
                continue;
            }
            //获得当前能匹配的子字符串
            String sub = s.substring(start, i+1);
            //开始缩减窗口
            for (; start <= i; start++) {
                Character left = s.charAt(start);
                if (!tMap.containsKey(left)) {

                    continue;
                }
                int charNum = smap.get(left);
                //如果当前子串可向右缩减
                if (smap.get(left) - 1 >= tMap.get(left)) {
                    // 减去当前字符数 后 继续向右缩减
                    smap.put(left, smap.getOrDefault(left, 0) - 1);

                } else {
                    /*
                      当前不可缩减时
                      1-获取当前子
                      2- 准备下一个子串的探测  从start+1处开始
                     */
                    sub = s.substring(start, i+1);
                    smap.put(left, smap.getOrDefault(left, 0) - 1);
                    start++;
                    break;
                }
            }
            //缩减窗口完毕 处理结果 右指针继续向右探测
            if (result == "") {
                result = sub;
            }else {
                result = result.length() > sub.length() ? sub : result;
            }
            if (result.length() == sLen) {
                return result;
            }

        }

        return result;
    }

    //字符串是否匹配
    private static boolean match(Map<Character, Integer> tmap, Map<Character, Integer> smap) {
        for (Map.Entry<Character, Integer> entry : tmap.entrySet()) {
            if (entry.getValue() > smap.getOrDefault(entry.getKey(), 0)) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        System.out.println(minWindow("ABC", "CBA"));
       /* System.out.println(minWindow("ACCBDA", "AB"));
        //BANC
        System.out.println(minWindow("ADOBECODEBANC", "ABC"));
        System.out.println(minWindow("a", "a"));*/
    }
}
